1. Field of the Invention
The embodiments of the invention generally relate to a method and apparatus for configuring a configurable content-addressable memory (CAM) as either binary CAM or ternary CAM. More specifically, the embodiments of the invention use a selected metal overlay combined with the configurable CAM cell design to produce either binary CAM including two binary CAM cells or ternary CAM including a single ternary CAM cell with two search ports.
2. Description of the Related Art
In standard computer memory, e.g., random access memory (RAM), a user provides a memory address and the RAM returns a data word stored at the memory address. In contrast to standard computer memory, content-addressable memory (CAM) receives a data word from the user and searches the entire CAM memory, in a single operation, to determine whether the data word is stored anywhere within the CAM memory. Because CAM searches its entire memory in a single operation, it is much faster than RAM in search applications. However, there are cost disadvantages to CAM. Unlike a RAM chip, which has simple storage cells, each individual memory bit of a data word stored in CAM must have an associated comparison circuit to detect a possible match between each individual memory bit of the stored data word and an inputted search bit of a searched for data word. In addition, matched outputs from each individual memory bit of the stored data word must be combined with the outputs of other individual memory bits of the stored data word by additional circuitry in order to complete a data word match. This additional circuitry further increases the size and manufacturing cost of a CAM integrated circuit.
There are two types of CAM: binary CAM and ternary CAM. Binary CAMs provide for the storing and searching of binary bits, i.e., zero and one (0, 1), comprising a data word. Ternary CAMs provide for the storing of three states, i.e., zero, one, and a “don't care” bit (0, 1, X). The “don't care” bit of ternary CAM allows for increased accommodation in searching data words. For example, a ternary CAM may store the data word, “11XX0”, which will match any of the searched for data words, “11000”, 11010”, “11100”, and “11110”. The increased accommodation in searching data words with ternary CAM, however, requires additional circuitry for each individual bit of the stored data word in order to provide the three possible states. This additional circuitry results in a larger size and greater cost for ternary CAM cells, as compared to binary CAM cells.
CAM is often used in computer network devices. For example, when a network switch receives a data frame from one of its ports, it updates an internal address table with the frame's source address and the receiving port's identifier. The network switch then looks up the destination address of the data frame in the internal address table to determine to which port the data frame should be forwarded, and sends the data frame to its destination address on that port. The internal address table is usually implemented by a binary CAM so that the data frame is quickly forwarded to the proper port, reducing the network switch's latency.
Ternary CAMs are frequently used in network routers, where each address has a network address, which varies in size depending on the subnet configuration, and a host address, which occupies the remaining bits. The network address and the host address are distinguished by a network mask for each subnet of the network. Routing information to its destination in the network requires a router to look up a routing table, which contains each known destination address, the associated network mask, and routing information needed to route packets to the destination address. Routing is performed rapidly by a ternary CAM, which masks the host portion of the address with “don't care” bits. Ternary CAM, which masks the host address and compares the destination address in one operation, quickly retrieves the routing information needed to route packets to the destination address.
FIG. 1 illustrates a simplified block diagram of a conventional 3×4 bit binary CAM. The binary CAM cells are arranged into three horizontal words, each four bits long. The binary CAM cells contain both storage and comparison circuitry. The vertically paired search-lines apply, in parallel, the bits, 0 or 1, of the search data word to the binary CAM cells. The match-lines, which run horizontally, compare whether each bit of the search data word matches each bit of the stored data word of a row of binary CAM cells. If a match occurs, the match-line indicates a match.
FIG. 2 illustrates a simplified block diagram of a conventional 3×4 bit ternary CAM. Like the binary CAM cells of FIG. 1, the ternary CAM cells of FIG. 2 are arranged into three horizontal words, each four bits long. Similarly, the vertically paired search-lines apply, in parallel, the bits, 0 or 1, of the search data word to the ternary CAM cells. However, the storage and comparison circuitry of the ternary CAM cells may also store the “don't care” bit, X, and compare each individual “don't care” bit with a corresponding bit of the applied search data word. As indicated by FIG. 2, the presence of “don't care” bits in two of the three stored data words, allows two of three of the match-lines to be activated.
Referring to FIGS. 1 and 2, a binary or ternary CAM search begins with pre-charging all match-lines high, putting them all temporarily into the match state. Next, the search-line drivers broadcast the search data word onto the search-lines. Then, each CAM cell compares its stored bit or state against the bit on its corresponding search-lines. CAM cells with matching bits do not affect the match-line, but CAM cells with a mismatch pull the match-line down to ground. Ternary CAM cells storing an X operate as if a match had occurred. The aggregate result is that match-lines are pulled down for any search data word that has at least one individual bit mismatch. All other match-lines remain activated, i.e., high.
FIG. 3 illustrates a conventional static random access memory (SRAM)-based binary CAM cell. Two access transistors connect the word bit lines, WBL and WBL, to the storage data nodes, D and D, which store the data using positive feedback in back-to-back inverters of a conventional SRAM cell under control of the wordline, WWL. The comparison circuitry attached to the storage data nodes compares the data in the binary CAM cell with the data on the search-lines, SL and SL. A mismatch in a binary CAM cell creates a path to ground from the match-line through one of the series of transistor pairs. This conventional binary CAM cell comprises 10 transistors.
FIG. 4 illustrates a conventional SRAM-based ternary CAM cell. The ternary CAM cell stores an extra state compared to the binary CAM cell, the “don't care” state, which requires two storage cells. The conventional ternary CAM search operation compares the stored data word at data nodes, D0, D1, to the search data word on the search-lines SLx, SLy). The ternary CAM cell may be likened to a truth table with three entries, where D0=0 and D1=1 yields a truth state of “0”, D0=1 and D1=0 yields a truth state of “1”, and D0=0 and D1=0 yields the “don't care” state, “X”. The state D0=1 and D1=1 is undefined and is not used. This conventional ternary CAM cell comprises 16 transistors.
Computer network devices benefit from both binary CAM and ternary CAM in their respective functions. However, binary CAM cannot be used to implement ternary CAM, because it lacks the additional circuitry for storing and comparing the “don't care” state. Although ternary CAM may be used to implement a binary CAM result, such a use is costly because of the 16 transistors per bit overhead for a ternary CAM cell, when compared to the 10 transistors per bit of the binary CAM cell.
Conventional hardware compliers do not allow for an efficient and economic admixture of binary CAM and ternary CAM in networking integrated circuits. However, the higher performance capability of ternary CAM to prevent bottlenecks in increasingly larger and faster networks and the inexpensive requirements of binary CAM to point to a content address, argue for the efficient and economic admixture of binary CAM and ternary CAM in today's network devices.